// MARK：1.两数之和
function twoSum(nums, target) {
    let res = [];
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                res = [i, j]
            }
        }
    }
    return res;
};
// twoSum([2, 7, 11, 15], 9)
// console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]


// MARK：2.两数相加
// const addTwoNumbers = function (l1, l2) {
//     // l1.reverse();
//     // l2.reverse();
//     let sum1 = '';
//     let sum2 = '';
//     for (let i = 0; i < l1.length; i++) {
//         sum1 += l1[l1.length - i - 1];
//     }
//     sum1 = parseInt(sum1);
//     for (let i = 0; i < l2.length; i++) {
//         sum2 += l2[l2.length - i - 1];
//     }
//     sum2 = parseInt(sum2);
//     let sum = sum1 + sum2;
//     let sums = [];
//     let sumsReverse = [];
//     for (let i = sum.toString().length - 1; i >= 0; i--) {
//         sums[i] = parseInt(sum.toString()[i])
//     }
//     for (let i = 0; i < sums.length; i++) {
//         sumsReverse[sums.length - i - 1] = sums[i]
//     }
//     return sumsReverse;
// }
// console.log(addTwoNumbers([2, 4, 3], [5, 6, 4]));
// addTwoNumbers([2, 4, 3], [5, 6, 4])


// // 节点
// class ListNode {
//     val
//     next
//     constructor() {
//     }
//     constructor(val) {
//         this.val = val === undefined ? 0 : val
//     }
//     constructor(val, next) {
//         this.val = val === undefined ? 0 : val
//         this.next = next === undefined ? null : next
//     }
// }

// class LinkedList {
//     head
//     length
//     constructor() {
//     }
//     constructor(head, length) {
//         this.head = head === undefined ? null : head
//         this.length = length === undefined ? 0 : length
//     }

//     get(index) {
//         if (index < 0 || index >= this.length) return null
//         let cur = this.head
//     }
// }

// MARK：9.回文数
var isPalindrome = function (x) {
    let xStr = x.toString()
    if (xStr[0] === '-') {
        return false
    }
    let xStrReverse = ''
    for (let i = 0; i < xStr.length; i++) {
        xStrReverse += xStr[xStr.length - i - 1]
    }
    return x === parseInt(xStrReverse)
};
// console.log(isPalindrome(10) )
isPalindrome(10)


// MARK：13.罗马字符转数字 "LVIII"
var romanToInt = function (s) {
    let charsMap = {
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000
    }
    let res = 0
    for (let i = 0; i < s.length; i++) {
        if (i === s.length - 1) {
            res += charsMap[s[i]]
        } else {
            if (charsMap[s[i]] >= charsMap[s[i + 1]]) {
                res += charsMap[s[i]]
            } else {
                res -= charsMap[s[i]]
            }
        }
    }
    return res
};

// MARK：14.最长公共前缀
var longestCommonPrefix = function (strs) {
    let res = ""
    let minLength = 0
    let minLengthIndex = 0
    for (let i = 0; i < strs.length; i++) {
        if (strs[minLengthIndex].length >= strs[i].length) {
            minLengthIndex = i
            minLength = strs[i].length
        }
    }
    for (let j = 0; j < minLength; j++) {
        let num = 0
        if (strs.length === 1) {
            return strs[0]
        }
        while ((num + 1) < strs.length) {
            if (strs[num][j] === strs[num + 1][j]) {
                if ((num + 1) === strs.length - 1) {
                    res += strs[num][j]
                    break
                }
                else {
                    num++;
                }
            } else {
                // break
                return res
            }
        }
    }
    return res
};

// console.log(longestCommonPrefix(['flw', 'f']))


// var isValid = function (s) {
//     let strMap = {
//         "(": ")",
//         "[": "]",
//         "{": "}"
//     }
//     let res = ""
//     if (s.length === 0 || s.length % 2 !== 0) {
//         return false
//     }
//     for (let i = 0; i < s.length; i++) {
//         res += s[i]
//         if (s[i + 1] === ")" || s[i + 1] === "]" || s[i + 1] === "}") {
//             for (let j = 0; j < res.length; j++) {
//                 i++
//             }
//             let resReverse = ""
//             for (let j = 0; j < res.length; j++) {
//                 resReverse += strMap[res[res.length - j - 1]]
//             }
//             let b = true
//             for (let j = 0; j < res.length; j++) {
//                 console.log(s[j])
//                 // console.log(strMap[s[j]])
//                 console.log(resReverse[resReverse.length - j - 1])
//                 if (strMap[s[j]] !== resReverse[resReverse.length - j - 1]) {
//                     b = false
//                 }
//             }
//             return b
//             // if(!s[i])  return b
//         }
//     }
// };
// console.log(isValid("([{])}"))
// isValid("([])")

// MARK：20.有效的括号
var isValidStack = function (s) {
    if (s.length === 0) return true
    if (s.length % 2 !== 0) return false
    let map = {
        '(': ')',
        '[': ']',
        '{': '}'
    }
    let stack = []
    for (let i = 0; i < s.length; i++) {
        const char = s[i]
        if (map[char]) {
            stack.push(char)
        } else {
            if (stack.length === 0) return false; // 栈空，无匹配左括号
            const top = stack.pop()
            if (map[top] !== char) return false
        }
    }
    return stack.length === 0;
}


// MARK: 21.合并两个有序链表
var mergeTwoLinkList = function (list1, list2) {
    let p1 = list1
    let p2 = list2
    if (!p1) return p2
    if (!p2) return p1
    let dummy = new ListNode(-1)
    let current = dummy
    while (p1 && p2) {
        if (p1.val <= p2.val) {
            current.next = p1.next
            p1 = p1.next
        } else {
            current.next = p2.next
            p2 = p2.next
        }
        current = current.next
    }
    current.next = p1 ? p1 : p2;
    return dummy.next
}

// MARK: 26.删除有序数组中的重复项 2025.8.6
// [0,0,1,2,2,3,3,4,4,4,4] 11 0-9
// [ 0,1, 2, 3,  4] 
var removeDuplicates = function (nums) {
    let i = 0;
    while (i < nums.length - 1) {
        if (nums[i] == nums[i + 1]) {
            nums.splice(i, 1)
        } else {
            i++
        }
    }
    // return i+1
    return nums.length
};
// console.log(removeDuplicates([1,1,2]))

// MARK: 27.移除元素 2025.8.6
// [1,1,2],1 3 
var removeElement = function (nums, val) {
    let i = 0;
    while (i < nums.length) {
        if (nums[i] == val) {
            nums.splice(i,1)
          
        }else {
            i++
        }
    }
    return nums.length
};
// console.log(removeElement([1,1,2],1))

// MARK: 28.找出字符串中第一个匹配项的下标 2025.8.7
// [1,1,2],1 3 
var removeElement = function (nums, val) {
    let i = 0;
    while (i < nums.length) {
        if (nums[i] == val) {
            nums.splice(i,1)
          
        }else {
            i++
        }
    }
    return nums.length
};
// console.log(removeElement([1,1,2],1))
